package algorithm.graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.Vector;

/**
 * @author bingo
 * @Description  无权图最短路径--->广度优先遍历
 * @Date 2018/6/21
 */
public class ShortestPath {
    /**图的引用*/
    private Graph G;

    /**起始点*/
    private  int s;

    /**记录bfs的过程中节点是否被访问*/
    private boolean[]  visited;

    /**记录路径, from[i]表示查找的路径上i的上一个节点*/
    private int[] from;

    /**构造函数, 寻路算法, 寻找图graph从s点到其他点的路径*/
    public ShortestPath(Graph graph, int s) {
        this.G = graph;
        this.s = s;
        visited = new boolean[graph.n()];
        from = new int[G.n()];
        for(int i=0;i<G.n();i++){
            visited[i]=false;
            from[i] = -1;
        }
        Queue<Integer> queue = new LinkedList();
        queue.add(s);
        visited[s]=true;
        while(queue.size()!=0){
            int a = queue.poll();
            for(int i:graph.adj(a)){
               if(!visited[i]){
                   queue.add(i);
                   visited[i] = true;
                   from[i] =a;

               }

            }
        }

    }
    /**查询从s点到w点的路径, 存放在vec中**/
    public Vector path(int w){
        Stack<Integer> s = new Stack<Integer>();
        int p=w;
        while(p!=-1){
            s.push(p);
            p=from[p];
        }
        Vector<Integer> vector = new Vector<>();
        while (!s.empty()){
            vector.add(s.pop());
        }
        return  vector;
    }

    /**打印路径*/
    public void showPath(int w){

        Vector vector = this.path(w);
        for(int i=0;i<vector.size();i++){
            System.out.print(vector.elementAt(i));
            if(i==vector.size()-1){
                System.out.print("");
            }
            else{
                System.out.print("->");
            }
        }
        System.out.println();

    }

    public static void main(String[] args) {

        Graph sparseGraph= new SparseGraph(7,false);
        ReadGraph read = new ReadGraph();
        read.readGraph(sparseGraph,"demo/component3.txt");
        ShortestPath path = new ShortestPath(sparseGraph,0);
        path.showPath(6);
        System.out.println("-------------------------------");
        read.readGraph(sparseGraph,"demo/component3.txt");
        Path path2 = new Path(sparseGraph,0);
        path2.showPath(6);
    }
}
